package algorithm.dynamic_programming;

public class MinCoinsNoLimit {
    public static int minCoins(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return Integer.MAX_VALUE;
        }
        return process(arr, aim, 0);
    }

    public static int process(int[] arr, int rest, int index){
        if(index == arr.length)
            return rest == 0? 0 : Integer.MAX_VALUE;

        int min = Integer.MAX_VALUE;
        for (int i = 0; rest - i * arr[index] >= 0; i++) {
            int process = process(arr, rest - i * arr[index], index + 1);
            if(process != Integer.MAX_VALUE){
                min = Math.min(process + i, min);
            }
        }
        return min;
    }


    public static int minCoins2(int[] arr, int aim){
        if(arr == null || arr.length == 0){
            return Integer.MAX_VALUE;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        dp[arr.length][0] = 0;
        for (int i = 1; i <= aim ; i++) {
            dp[arr.length][i] = Integer.MAX_VALUE;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i + 1][j];
                if(j - arr[i] >= 0){
                    dp[i][j] = dp[i][j - arr[i]] != Integer.MAX_VALUE? Math.min(dp[i][j], dp[i][j - arr[i]] + 1) : dp[i][j];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {5, 6, 7, 10};
        int i = minCoins2(arr, 19);
        System.out.println(i);
    }
}
